package com.shm.leetcode;

/**
 * 1137. 第 N 个泰波那契数
 * 泰波那契序列 Tn 定义如下：
 *
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 *
 * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 4
 * 输出：4
 * 解释：
 * T_3 = 0 + 1 + 1 = 2
 * T_4 = 1 + 1 + 2 = 4
 * 示例 2：
 *
 * 输入：n = 25
 * 输出：1389537
 *
 *
 * 提示：
 *
 * 0 <= n <= 37
 * 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
 * @author SHM
 */
public class Tribonacci {
    /**
     * 两种思路：空间优化与性能优化
     * 有两种思路。一种是性能优化，一种是空间优化。
     *
     * 首先介绍性能优化
     *
     * 已知 nn 小于 38，可以先将斐波那契数列的前 38 项计算出来，保存在一个静态数组中。每次执行测试用例时，直接检索对应数字即可。
     *
     * 如何计算斐波那契数列？
     *
     * 两种方法：带记忆的递归和动态计算。这两种方法计算 NN 个斐波那契数列都需要 NN 步操作。类似 tribonacci(k) = tribonacci(k - 1) + tribonacci(k - 2) + tribonacci(k - 3) 这种简单递归不在讨论之列，因为这种递归方法的复杂度达到 3^N3
     * N
     *  。
     *
     * 初步计算所有斐波那契数保存在静态数组的方法，运行时性能为 O(1)O(1)，但是需要 O(N)O(N) 的空间记录 NN 个斐波那契数。在保证性能的同时优化空间也非常重要。
     *
     * 在不允许占用大量空间的情况下，可以使用动态计算的方法，在内存中保留不超过 3 个斐波那契数即可。
     *
     *
     *
     * 方法一：空间优化：动态计算
     * 如果 n < 3，答案可直接得出。
     *
     * 否则，初始化前 3 个斐波那契数字 x = 0, y = z = 1，并执行 n - 2 步循环。循环的每一步：
     *
     * 令 x = y。
     *
     * 令 y = z。
     *
     * 令 z = x + y + z。
     *
     * 返回 z。
     * 复杂度分析
     *
     * 时间复杂度：\mathcal{O}(N)O(N)。
     *
     * 空间复杂度：\mathcal{O}(1)O(1)，保存最后 3 个斐波那契数。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number/solution/di-n-ge-tai-bo-na-qi-shu-by-leetcode/
     * @param n
     * @return
     */
    public int tribonacci(int n) {
        if(n==0){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        int t0=0,t1=1,t2=1;
        for(int i=3;i<=n;i++){
            int t3 = t0+t1+t2;;
            t0=t1;
            t1=t2;
            t2=t3;
        }
        return t2;
    }

    /**
     * 方法三：性能优化：动态计算
     * 预计算 38 个斐波那契数：
     *
     * 初始化一个数组用于保存斐波那契数，并初始化前 3 个斐波那契数字。
     *
     * i 从 3 循环到 38，每一步计算出一个新的斐波那契数：nums[i] = helper(i - 1) + helper(i - 2) + helper(i - 3)。
     *
     * 从数组中检索所需的斐波那契数。
     * 复杂度分析
     *
     * 时间复杂度：\mathcal{O}(1)O(1)，预计算 38 个斐波那契数字，并在数组中检索。
     *
     * 空间复杂度：\mathcal{O}(1)O(1)，存储 38 个斐波那契数字的数组。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number/solution/di-n-ge-tai-bo-na-qi-shu-by-leetcode/
     * @param n
     * @return
     */
    public int tribonacci_2(int n) {
        return new Tri().nums[n];
    }

    class Tri {
        private int n = 38;
        public int[] nums = new int[n];
        Tri() {
            nums[1] = 1;
            nums[2] = 1;
            for (int i = 3; i < n; ++i) {
                nums[i] = nums[i - 1] + nums[i - 2] + nums[i - 3];
            }
        }
    }

}
